#ifndef _HEAP_H_
#define _HEAP_H_

#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
class MyHeap
{
private:
	typedef    bool (*COMP_FUNC)(const T&, const T&);
	COMP_FUNC _comp;
	vector<T> _data;
public:
	MyHeap(COMP_FUNC compare_function = NULL):_comp(compare_function)
	{ 
		if(NULL == _comp)
			make_heap(_data.begin(), _data.end());
		else
			make_heap(_data.begin(), _data.end(), _comp);
	} 
	void push(const T& item)
	{ 
		_data.push_back(item);
		if(NULL == _comp)
			push_heap(_data.begin(), _data.end());
		else
			push_heap(_data.begin(), _data.end(), _comp); 
	}
	T pop()
	{ 
		if(isEmpty())
	        throw "empty heap";
		if(NULL == _comp)
			pop_heap(_data.begin(), _data.end());
		else
			pop_heap(_data.begin(), _data.end(), _comp);
		T removed = _data.back();
		_data.pop_back();
		return removed;
	} 
	T top()
	{
		if(isEmpty())
	        throw "empty heap";
	    return _data[0];
	}
	bool isEmpty() const
	{
		return _data.empty();
	} 
	void clear()
	{
		_data.clear();
	}
	unsigned int size()
	{
		return _data.size();
	}
};



#endif